
import java.util.*;

/**
 * @program: leetcode015
 * @author: JCM
 * @create: 2022-11-26 14:58
 * @description: 三数之和
 **/
public class LeetCode015 {
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            int len = nums.length;
            // 小于三个数 无结果
            if(nums == null || len < 3) {
                return ans;
            }
            Arrays.sort(nums);
            for(int i = 0; i < len; i++) {
                if(nums[i] > 0) break; // 第一个数大于 0 则无结果直接跳出
                if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
                int l = i+1;
                int r = len-1;
                while(l < r) {
                    int sum = nums[i] + nums[l] + nums[r];
                    if(sum == 0) {
                        ans.add(Arrays.asList(nums[i],nums[l],nums[r]));
                        // 相同的数据直接跳过
                        while(l < r && nums[l] == nums[l+1]) l++;
                        while(l < r && nums[r] == nums[r-1]) r--;
                        l++;
                        r--;
                    }else if(sum < 0) {
                        l++;
                    }else {
                        r--;
                    }
                }
            }
            return ans;
        }
    }
}
